from __future__ import nested_scopes
import Consommateur as C
import Producteur as P
import Set as S
from math import *
import numpy as np
import scipy.optimize as s
import random as r

"""Resultat en metre
Distance(Producteur p, Consommateur c"""

d=[[56.0921545309,412.902036059,297.5333736374,285.2234197985,229.0978201421,268.7955740074,247.0905749746,395.9514441317,44.7437460488,338.2824193583,395.5008744783,463.1932582293,338.2923921014,66.4697945551,267.8320107274,253.6805294308,316.1612918266,108.2976948333,423.7962776839],
[549.0356987475,255.2266783435,525.7766913891,859.6659156619,468.4109650187,871.8262544252,387.1309149898,424.6423265084,565.2851620552,802.8818670808,741.0362188334,141.8487222428,903.4337380964,669.2337347976,762.230196629,780.1504197038,465.7267975823,540.0467590442,407.9058353089],
[279.2117628076,285.9500478678,201.7887494971,548.4053290248,327.8887849088,584.1531517395,242.3835152552,144.3495426377,309.548879482,475.6365748661,623.8295909053,196.820953135,669.4757649611,390.8542809918,566.8603113559,567.8201004865,145.7012377876,320.7255034278,151.0347151825],
[522.1337467968,281.9323238448,464.6717026802,819.2555660973,472.5514630258,842.5536343254,384.4269269802,354.071770886,543.0738335699,747.7570469553,759.6158117891,124.6629808692,893.0589039939,641.6787745336,761.2386630285,774.718586209,403.4459007338,527.3225250375,334.7249041898],
[509.6101307836,446.1767551201,331.7855285207,733.779404429,555.8119152125,793.2320175383,465.2928271937,194.4613751298,542.4558193411,612.7679446253,855.1749396747,282.6254841643,900.1768500184,612.8161606092,803.2786220915,803.1100980134,276.8748687455,557.2895865736,163.3516205646],
[222.6805445533,200.8151058884,426.3483074066,535.0024197169,26.8171524372,494.6969750158,80.0218854537,452.0982350485,207.848632883,576.0980635994,313.8403872774,327.9726023246,470.0865570307,310.4827889028,318.833657707,341.3781656667,405.9378769806,145.4766865288,467.340684758],
[102.0386766528,467.5812394001,260.3935903961,227.4403427683,299.7261614224,241.5329796069,305.6523294241,376.6484081598,113.7770443634,263.7972115728,462.7391738938,496.0788777349,358.8416068212,66.1936865132,320.0665870145,297.7474520001,292.1206397779,181.0675778035,406.7109392535],
[529.0625057361,514.2315757676,316.325429686,719.5854505083,601.7454559336,790.967438768,514.1799956362,185.5155177495,564.295408831,581.857014395,897.935001437,356.8443509396,915.1304763443,622.5218265055,831.0255993911,826.6125096226,270.925822293,588.0612079767,155.3682156712],
[424.4343260012,466.6323460605,205.450466974,609.3085444192,517.544323797,679.6681789322,435.2290060165,75.6038561629,460.6481959697,477.9772533319,807.5119627529,332.0491630846,806.9242607541,513.3527810602,729.1935152567,722.3685205954,160.0743390566,490.0104757992,48.5902984164],
[319.2435923482,676.2004757502,464.2796270561,111.3705136795,471.4583837638,17.9798369993,509.5801229124,594.9565055601,308.4047616669,296.979125931,496.2009871092,726.4707255706,231.0638469265,199.8102362606,313.8143689637,270.4274090593,509.3322914637,355.0500865644,626.2173073847],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728],
[186.8168581986,544.8075453857,365.6427777963,169.4805803313,346.8690513428,136.0576758663,378.3120865176,486.8499413739,176.1431687141,287.6086779664,430.0350798423,594.6851220901,258.4528825808,67.0797197431,261.1425294294,227.4077080309,401.7693469217,227.0683941403,517.2129493759],
[268.8985716026,420.2611575523,531.9174933887,456.3792450784,200.1916851086,368.247282995,288.7377950364,604.1175401502,231.7051320711,569.0711575642,147.840487193,547.7093040642,268.4236311164,263.2179126415,103.3685155017,138.5081452614,535.9683980951,186.0236419889,626.8571833509],
[324.2843221192,442.4949040531,95.6121164626,499.4924379915,445.3801551732,568.3765563519,373.1338171396,42.4214352075,361.5812066858,378.3429778138,722.9091217272,343.419376908,699.6893859204,405.351724028,630.5604798964,620.5748708715,51.2882406694,398.9677078437,73.2557422084],
[734.2499071431,367.9553098186,802.796461078,1062.1160422432,571.8837414295,1037.8082233955,532.1166823285,727.1610986467,734.7640299951,1052.3623974811,745.3102095528,410.5360127503,1002.5552416697,844.0750969465,839.1611341429,871.3550324739,748.5689017813,684.0951103545,716.2538288695],
[292.6422457015,364.1781683998,137.2068805724,519.052801301,383.3925755657,571.4159721464,304.8873377727,71.3138232795,327.7030050382,422.8681162961,670.9721989889,268.4236385947,680.7034202223,390.8047301311,594.823866027,590.0218366922,76.0290574672,353.7306539202,88.4665225414],
[150.8057373853,231.7378151409,354.0582385644,472.3103818737,65.9471881014,445.0009483008,66.7769002579,391.3331936301,142.3734007226,502.2748156105,352.7713480468,321.3928870707,451.2684170287,250.5263239196,316.6212821663,329.6651153754,338.1068723437,92.2635346764,409.5330078009],
[57.4474618125,340.8036728834,218.6617434725,360.1553268265,214.5996207876,370.3133258983,188.4369641419,294.4217253318,92.1484210512,356.2857371508,457.4309431029,362.1699104955,448.2306891103,170.5413585645,360.7699863796,354.3942539882,221.2125167261,131.6268688169,320.2487826787],
[354.9148534124,56.2771011454,423.8016612392,680.5454988278,245.9604307269,672.9661814328,169.0279444122,377.9512647614,363.0717256688,662.431006858,523.693695328,119.4901089526,684.8565375156,471.8011149687,540.1464399033,559.4840894681,375.9414760633,326.8721031915,378.0031326213],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[558.8953614054,585.2596684973,320.4305648824,713.4362996923,653.8893743162,796.0510671335,569.8629952304,209.5507316436,595.6449871838,560.1674726838,944.9843801253,433.3547956776,935.9747444693,641.5225623928,864.6683983831,856.3101051855,287.8651143034,627.1027199756,185.8788120619],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[558.8953614054,585.2596684973,320.4305648824,713.4362996923,653.8893743162,796.0510671335,569.8629952304,209.5507316436,595.6449871838,560.1674726838,944.9843801253,433.3547956776,935.9747444693,641.5225623928,864.6683983831,856.3101051855,287.8651143034,627.1027199756,185.8788120619],
[313.2464634692,130.5111583941,348.0172081329,630.5708166707,253.4974665624,635.943231199,162.955001241,299.5375724343,328.6904226133,596.8578427491,548.8003335644,99.2453484039,671.5904290594,433.2480498656,538.7944110589,552.1472181197,298.3451734713,306.1439483109,300.5771071508],
[286.567124362,207.9293267357,273.5273417456,586.0762141866,282.7247770939,605.974865376,191.3494979486,221.4736558727,309.8976687485,534.2040138642,582.6548438185,134.1774222146,666.400596426,405.4950178951,547.8662608721,554.9766934991,221.2993720345,303.9690862293,224.3203612627],
[318.4440537597,619.3800975925,184.4086699699,273.6912115691,516.8199571992,381.4049688071,487.0826959553,313.1366654944,348.2140122643,109.635917344,714.2549403548,576.6192953267,568.4975288017,310.0617455446,566.3277095456,538.4168079085,245.982888225,413.9463724602,342.3950117709],
[215.5939050134,435.308612349,478.1668797945,384.1256435627,208.7320895948,301.1692230252,285.4794707829,561.8037979126,177.8414229368,497.2553835886,216.3647285959,543.9412695632,235.3352030942,192.172793474,96.6082810473,107.8262568724,488.5568761053,149.7810905156,586.6453523356],
[268.8985716026,420.2611575523,531.9174933887,456.3792450784,200.1916851086,368.247282995,288.7377950364,604.1175401502,231.7051320711,569.0711575642,147.840487193,547.7093040642,268.4236311164,263.2179126415,103.3685155017,138.5081452614,535.9683980951,186.0236419889,626.8571833509],
[661.3964615515,644.3943726502,430.5279765294,824.7250588333,740.0417444534,906.8065412979,652.2731994362,312.3307222738,697.4298613818,669.511878569,1036.0519991163,480.2337724197,1042.98482486,748.8237214555,965.5356132345,959.3500217074,394.4394725447,724.240950882,285.1012668744],
[85.5144472218,281.028874371,284.0801773466,413.4032371687,139.5031700376,402.6902227099,119.0014246959,337.4957710662,93.2718681256,428.9052698413,401.7032162209,333.4078594725,443.7934091548,200.8078375568,331.2847773569,334.2125152467,275.1315149865,85.0482899409,359.3038589096],
[85.5144472218,281.028874371,284.0801773466,413.4032371687,139.5031700376,402.6902227099,119.0014246959,337.4957710662,93.2718681256,428.9052698413,401.7032162209,333.4078594725,443.7934091548,200.8078375568,331.2847773569,334.2125152467,275.1315149865,85.0482899409,359.3038589096],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[57.4474618125,340.8036728834,218.6617434725,360.1553268265,214.5996207876,370.3133258983,188.4369641419,294.4217253318,92.1484210512,356.2857371508,457.4309431029,362.1699104955,448.2306891103,170.5413585645,360.7699863796,354.3942539882,221.2125167261,131.6268688169,320.2487826787],
[177.8664571875,462.4073716676,430.8920854961,312.0535375131,241.0575221148,237.0985027488,301.387850819,527.1170428969,143.1662580581,426.0776586782,286.9076546108,550.8595620823,221.2474663375,123.8808075681,135.9005856827,120.5381309228,448.9083511842,145.6146134845,554.0546668724],
[57.4474618125,340.8036728834,218.6617434725,360.1553268265,214.5996207876,370.3133258983,188.4369641419,294.4217253318,92.1484210512,356.2857371508,457.4309431029,362.1699104955,448.2306891103,170.5413585645,360.7699863796,354.3942539882,221.2125167261,131.6268688169,320.2487826787],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[102.0386766528,467.5812394001,260.3935903961,227.4403427683,299.7261614224,241.5329796069,305.6523294241,376.6484081598,113.7770443634,263.7972115728,462.7391738938,496.0788777349,358.8416068212,66.1936865132,320.0665870145,297.7474520001,292.1206397779,181.0675778035,406.7109392535],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728],
[284.557132086,564.2738795933,524.6970397194,312.6689419024,338.5298138407,201.0155631008,407.852613727,630.0697674075,252.1314000587,466.3229968389,282.7422497584,660.8797698022,110.1135694008,200.0742296021,100.0067749185,55.8557957958,549.1729283817,255.6642658858,658.0857371049],
[393.8171957834,669.1521551478,624.2727596916,350.5865167031,442.5788938823,222.2035668515,516.3666493709,735.4573146673,362.5291341977,527.3720260904,319.9035813061,771.2716362004,9.1273800901,299.1558332556,162.2206624192,128.4267873632,653.021773824,366.4811283055,764.1671881962],
[284.557132086,564.2738795933,524.6970397194,312.6689419024,338.5298138407,201.0155631008,407.852613727,630.0697674075,252.1314000587,466.3229968389,282.7422497584,660.8797698022,110.1135694008,200.0742296021,100.0067749185,55.8557957958,549.1729283817,255.6642658858,658.0857371049],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[549.0356987475,255.2266783435,525.7766913891,859.6659156619,468.4109650187,871.8262544252,387.1309149898,424.6423265084,565.2851620552,802.8818670808,741.0362188334,141.8487222428,903.4337380964,669.2337347976,762.230196629,780.1504197038,465.7267975823,540.0467590442,407.9058353089],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[179.792240663,220.7222786792,255.6836185744,494.7843023001,193.1508407434,502.2894374985,114.0050921766,262.8496997404,199.9409182871,471.4787960276,487.8955941431,228.4538478884,555.0939519029,299.9739372319,438.8195783018,444.3613372068,223.4909449584,193.4513085965,278.0687541743],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[315.2796606446,658.0133779748,273.8209929052,166.1084069692,519.0075539399,283.6007036624,508.927900067,409.8007212397,335.607940204,41.0980121329,672.0066805818,641.9799589121,484.1179870011,264.9531842659,508.5904638328,474.8786968137,333.6384069539,403.5391823211,440.4611218708],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[585.239841541,252.1097085376,591.2443927795,904.7945286178,477.3234254631,906.586494587,405.5281039099,498.1453340837,596.9572154384,861.5145951218,730.0954801956,194.2023275932,919.9314229201,704.2829483396,770.859216728,792.9494445184,532.670098175,563.4162470582,483.3932174646],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[149.069224813,330.4659773849,405.7336202326,415.857621564,107.5525917099,363.2905054212,174.8914587817,471.1684703815,116.4401301569,487.2408756833,270.6346720159,432.6556081728,342.2304358264,193.5419528876,205.910866661,218.5427544477,405.115908382,55.5139249773,493.5098106849],
[315.2796606446,658.0133779748,273.8209929052,166.1084069692,519.0075539399,283.6007036624,508.927900067,409.8007212397,335.607940204,41.0980121329,672.0066805818,641.9799589121,484.1179870011,264.9531842659,508.5904638328,474.8786968137,333.6384069539,403.5391823211,440.4611218708],
[501.7501237512,382.6974059107,364.3265419182,755.5627369076,517.7521983539,802.7822596892,425.5585889898,232.6127032154,531.3037848057,651.5848173165,817.3849822807,213.122201087,891.4128597898,612.8488747739,782.0599187326,786.3624644479,304.3723317132,536.2185813913,205.3873690854],
[315.2796606446,658.0133779748,273.8209929052,166.1084069692,519.0075539399,283.6007036624,508.927900067,409.8007212397,335.607940204,41.0980121329,672.0066805818,641.9799589121,484.1179870011,264.9531842659,508.5904638328,474.8786968137,333.6384069539,403.5391823211,440.4611218708],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[179.792240663,220.7222786792,255.6836185744,494.7843023001,193.1508407434,502.2894374985,114.0050921766,262.8496997404,199.9409182871,471.4787960276,487.8955941431,228.4538478884,555.0939519029,299.9739372319,438.8195783018,444.3613372068,223.4909449584,193.4513085965,278.0687541743],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728],
[451.3420987242,538.8755484617,714.3582619251,596.9939849042,350.0934703113,486.5693942228,442.315556395,782.9835032201,414.0547041627,734.0599508522,53.0569888582,689.7838623421,312.2219205711,433.4954772639,189.3329107735,230.7152262053,717.1881662825,366.7427012332,804.4655094266],
[509.6101307836,446.1767551201,331.7855285207,733.779404429,555.8119152125,793.2320175383,465.2928271937,194.4613751298,542.4558193411,612.7679446253,855.1749396747,282.6254841643,900.1768500184,612.8161606092,803.2786220915,803.1100980134,276.8748687455,557.2895865736,163.3516205646],
[643.4381432838,732.7163705967,381.8399202998,725.8255518346,771.6124122046,827.521548941,694.8872464437,318.7149829842,681.2296161516,548.390413637,1049.5664832847,589.6352296158,993.7353458913,704.0268392308,947.0012307178,931.7829484285,374.1164464554,724.3637618689,306.9766348861],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[57.4474618125,340.8036728834,218.6617434725,360.1553268265,214.5996207876,370.3133258983,188.4369641419,294.4217253318,92.1484210512,356.2857371508,457.4309431029,362.1699104955,448.2306891103,170.5413585645,360.7699863796,354.3942539882,221.2125167261,131.6268688169,320.2487826787],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[395.8523982032,250.0521356186,330.1981640722,683.3181447426,383.8480034505,711.963469254,291.5711689374,231.9164594844,420.5713067789,610.9048444559,682.4215169647,92.7257320508,777.7107228401,513.4679399452,657.6732122593,665.8261046474,269.7646740818,414.9151736022,219.2976123815],
[520.5701466229,325.3137193608,724.4487175949,805.1977148885,317.8139187987,734.617060779,361.4024387783,727.5553584093,498.4214642858,873.4527301055,323.1234664006,495.9995312615,629.8587447633,585.4641783314,465.0913706034,506.6684858684,696.4035237471,430.5958964337,736.0032007151],
[424.4343260012,466.6323460605,205.450466974,609.3085444192,517.544323797,679.6681789322,435.2290060165,75.6038561629,460.6481959697,477.9772533319,807.5119627529,332.0491630846,806.9242607541,513.3527810602,729.1935152567,722.3685205954,160.0743390566,490.0104757992,48.5902984164],
[727.4145666934,518.7017935143,600.2456092646,992.8875636894,705.8589500445,1036.631421931,615.5493185966,465.4390504242,753.7320388884,886.1103497956,996.4656094103,359.2685173366,1111.651533892,842.6186925658,989.1181172379,998.9990191293,541.1264124369,748.4172521668,435.9511942364],
[102.0386766528,467.5812394001,260.3935903961,227.4403427683,299.7261614224,241.5329796069,305.6523294241,376.6484081598,113.7770443634,263.7972115728,462.7391738938,496.0788777349,358.8416068212,66.1936865132,320.0665870145,297.7474520001,292.1206397779,181.0675778035,406.7109392535],
[284.557132086,564.2738795933,524.6970397194,312.6689419024,338.5298138407,201.0155631008,407.852613727,630.0697674075,252.1314000587,466.3229968389,282.7422497584,660.8797698022,110.1135694008,200.0742296021,100.0067749185,55.8557957958,549.1729283817,255.6642658858,658.0857371049],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[102.0386766528,467.5812394001,260.3935903961,227.4403427683,299.7261614224,241.5329796069,305.6523294241,376.6484081598,113.7770443634,263.7972115728,462.7391738938,496.0788777349,358.8416068212,66.1936865132,320.0665870145,297.7474520001,292.1206397779,181.0675778035,406.7109392535],
[85.5144472218,281.028874371,284.0801773466,413.4032371687,139.5031700376,402.6902227099,119.0014246959,337.4957710662,93.2718681256,428.9052698413,401.7032162209,333.4078594725,443.7934091548,200.8078375568,331.2847773569,334.2125152467,275.1315149865,85.0482899409,359.3038589096],
[679.2320657096,314.1450725178,730.4821992378,1006.5789619534,530.7191958504,990.1486438223,480.7254792575,649.9097088587,683.0313908669,986.7366038498,732.2676963469,334.5583578821,969.9194882191,792.6659750115,809.8315534866,839.0991238884,674.8904960249,636.8771428491,637.9638198798],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728],
[324.2843221192,442.4949040531,95.6121164626,499.4924379915,445.3801551732,568.3765563519,373.1338171396,42.4214352075,361.5812066858,378.3429778138,722.9091217272,343.419376908,699.6893859204,405.351724028,630.5604798964,620.5748708715,51.2882406694,398.9677078437,73.2557422084],
[149.069224813,330.4659773849,405.7336202326,415.857621564,107.5525917099,363.2905054212,174.8914587817,471.1684703815,116.4401301569,487.2408756833,270.6346720159,432.6556081728,342.2304358264,193.5419528876,205.910866661,218.5427544477,405.115908382,55.5139249773,493.5098106849],
[57.4474618125,340.8036728834,218.6617434725,360.1553268265,214.5996207876,370.3133258983,188.4369641419,294.4217253318,92.1484210512,356.2857371508,457.4309431029,362.1699104955,448.2306891103,170.5413585645,360.7699863796,354.3942539882,221.2125167261,131.6268688169,320.2487826787],
[395.8523982032,250.0521356186,330.1981640722,683.3181447426,383.8480034505,711.963469254,291.5711689374,231.9164594844,420.5713067789,610.9048444559,682.4215169647,92.7257320508,777.7107228401,513.4679399452,657.6732122593,665.8261046474,269.7646740818,414.9151736022,219.2976123815],
[241.9573881545,591.5146374191,247.0428811074,157.6280413481,445.2935109156,249.8553281155,438.6438299364,383.9843889657,261.2760940082,114.9402284044,601.4368780507,587.2795003942,434.4385197215,193.06830737,442.6238343356,411.3861006297,301.6840049865,329.1649155322,415.4704772204],
[177.8664571875,462.4073716676,430.8920854961,312.0535375131,241.0575221148,237.0985027488,301.387850819,527.1170428969,143.1662580581,426.0776586782,286.9076546108,550.8595620823,221.2474663375,123.8808075681,135.9005856827,120.5381309228,448.9083511842,145.6146134845,554.0546668724],
[274.5694298452,96.7226289451,410.2628080534,601.925053624,134.9665920098,580.0210174769,71.3817522608,401.550168412,274.0853649319,610.7307605977,417.1155703321,220.2964881385,576.7281021613,383.5528978686,429.3190667487,449.8773651853,375.0745230825,227.18718079,410.2061992824],
[286.567124362,207.9293267357,273.5273417456,586.0762141866,282.7247770939,605.974865376,191.3494979486,221.4736558727,309.8976687485,534.2040138642,582.6548438185,134.1774222146,666.400596426,405.4950178951,547.8662608721,554.9766934991,221.2993720345,303.9690862293,224.3203612627],
[395.8523982032,250.0521356186,330.1981640722,683.3181447426,383.8480034505,711.963469254,291.5711689374,231.9164594844,420.5713067789,610.9048444559,682.4215169647,92.7257320508,777.7107228401,513.4679399452,657.6732122593,665.8261046474,269.7646740818,414.9151736022,219.2976123815],
[177.8664571875,462.4073716676,430.8920854961,312.0535375131,241.0575221148,237.0985027488,301.387850819,527.1170428969,143.1662580581,426.0776586782,286.9076546108,550.8595620823,221.2474663375,123.8808075681,135.9005856827,120.5381309228,448.9083511842,145.6146134845,554.0546668724],
[241.9573881545,591.5146374191,247.0428811074,157.6280413481,445.2935109156,249.8553281155,438.6438299364,383.9843889657,261.2760940082,114.9402284044,601.4368780507,587.2795003942,434.4385197215,193.06830737,442.6238343356,411.3861006297,301.6840049865,329.1649155322,415.4704772204],
[629.1373018007,273.3898539275,659.7690899248,953.9653653047,498.5880623289,946.2244993366,437.6413523935,573.4456304994,636.6751926755,922.9787170443,727.1402535081,261.3785863666,942.2277799389,745.7654706181,786.8731520351,812.7656993973,602.7160345806,596.1771182965,560.2467815279],
[177.8664571875,462.4073716676,430.8920854961,312.0535375131,241.0575221148,237.0985027488,301.387850819,527.1170428969,143.1662580581,426.0776586782,286.9076546108,550.8595620823,221.2474663375,123.8808075681,135.9005856827,120.5381309228,448.9083511842,145.6146134845,554.0546668724],
[85.5144472218,281.028874371,284.0801773466,413.4032371687,139.5031700376,402.6902227099,119.0014246959,337.4957710662,93.2718681256,428.9052698413,401.7032162209,333.4078594725,443.7934091548,200.8078375568,331.2847773569,334.2125152467,275.1315149865,85.0482899409,359.3038589096],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[293.4139987123,307.6271050296,535.6029131511,554.603611197,125.3438565009,483.9511994101,214.080476751,578.2539044696,263.9987433347,636.1360193165,181.908092888,455.5131552246,401.9597978622,338.2793980915,236.3370144828,271.753613844,524.2080370401,197.6368546854,595.7262564431],
[558.8953614054,585.2596684973,320.4305648824,713.4362996923,653.8893743162,796.0510671335,569.8629952304,209.5507316436,595.6449871838,560.1674726838,944.9843801253,433.3547956776,935.9747444693,641.5225623928,864.6683983831,856.3101051855,287.8651143034,627.1027199756,185.8788120619],
[85.5144472218,281.028874371,284.0801773466,413.4032371687,139.5031700376,402.6902227099,119.0014246959,337.4957710662,93.2718681256,428.9052698413,401.7032162209,333.4078594725,443.7934091548,200.8078375568,331.2847773569,334.2125152467,275.1315149865,85.0482899409,359.3038589096],
[241.9573881545,591.5146374191,247.0428811074,157.6280413481,445.2935109156,249.8553281155,438.6438299364,383.9843889657,261.2760940082,114.9402284044,601.4368780507,587.2795003942,434.4385197215,193.06830737,442.6238343356,411.3861006297,301.6840049865,329.1649155322,415.4704772204],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[56.0921545309,412.902036059,297.5333736374,285.2234197985,229.0978201421,268.7955740074,247.0905749746,395.9514441317,44.7437460488,338.2824193583,395.5008744783,463.1932582293,338.2923921014,66.4697945551,267.8320107274,253.6805294308,316.1612918266,108.2976948333,423.7962776839],
[149.069224813,330.4659773849,405.7336202326,415.857621564,107.5525917099,363.2905054212,174.8914587817,471.1684703815,116.4401301569,487.2408756833,270.6346720159,432.6556081728,342.2304358264,193.5419528876,205.910866661,218.5427544477,405.115908382,55.5139249773,493.5098106849],
[274.5694298452,96.7226289451,410.2628080534,601.925053624,134.9665920098,580.0210174769,71.3817522608,401.550168412,274.0853649319,610.7307605977,417.1155703321,220.2964881385,576.7281021613,383.5528978686,429.3190667487,449.8773651853,375.0745230825,227.18718079,410.2061992824],
[506.0241717405,326.4854047402,409.8962929486,784.3000425348,489.4131335064,819.3619468936,397.7367327795,288.6069229999,531.5142025687,696.982515423,785.2894182648,154.837343783,889.0230232811,622.6184289092,767.9143589574,776.809378851,348.3488226388,526.0186273986,265.7775144936],
[241.9573881545,591.5146374191,247.0428811074,157.6280413481,445.2935109156,249.8553281155,438.6438299364,383.9843889657,261.2760940082,114.9402284044,601.4368780507,587.2795003942,434.4385197215,193.06830737,442.6238343356,411.3861006297,301.6840049865,329.1649155322,415.4704772204],
[558.8953614054,585.2596684973,320.4305648824,713.4362996923,653.8893743162,796.0510671335,569.8629952304,209.5507316436,595.6449871838,560.1674726838,944.9843801253,433.3547956776,935.9747444693,641.5225623928,864.6683983831,856.3101051855,287.8651143034,627.1027199756,185.8788120619],
[84.1613308649,366.0755579603,347.5622357908,348.9377235249,162.4652632626,311.1265884556,200.2677319322,428.3583411828,46.972086648,412.7667230572,330.8425129735,441.4889580375,332.5050956679,124.2758406757,227.4167663777,225.2157918285,355.2757434166,42.7389038973,453.4872794841],
[549.0356987475,255.2266783435,525.7766913891,859.6659156619,468.4109650187,871.8262544252,387.1309149898,424.6423265084,565.2851620552,802.8818670808,741.0362188334,141.8487222428,903.4337380964,669.2337347976,762.230196629,780.1504197038,465.7267975823,540.0467590442,407.9058353089],
[268.8985716026,420.2611575523,531.9174933887,456.3792450784,200.1916851086,368.247282995,288.7377950364,604.1175401502,231.7051320711,569.0711575642,147.840487193,547.7093040642,268.4236311164,263.2179126415,103.3685155017,138.5081452614,535.9683980951,186.0236419889,626.8571833509],
[222.6805445533,200.8151058884,426.3483074066,535.0024197169,26.8171524372,494.6969750158,80.0218854537,452.0982350485,207.848632883,576.0980635994,313.8403872774,327.9726023246,470.0865570307,310.4827889028,318.833657707,341.3781656667,405.9378769806,145.4766865288,467.340684758],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728],
[354.9148534124,56.2771011454,423.8016612392,680.5454988278,245.9604307269,672.9661814328,169.0279444122,377.9512647614,363.0717256688,662.431006858,523.693695328,119.4901089526,684.8565375156,471.8011149687,540.1464399033,559.4840894681,375.9414760633,326.8721031915,378.0031326213],
[222.6805445533,200.8151058884,426.3483074066,535.0024197169,26.8171524372,494.6969750158,80.0218854537,452.0982350485,207.848632883,576.0980635994,313.8403872774,327.9726023246,470.0865570307,310.4827889028,318.833657707,341.3781656667,405.9378769806,145.4766865288,467.340684758],
[220.3617818329,309.9700491566,469.0200061971,484.6479792943,89.4766428091,421.6463590237,180.2633872215,521.8217851177,189.8838618959,561.6988655724,218.6006822643,437.4749606078,366.2331003418,265.4364501641,209.2326397001,235.5221275124,462.2185339079,124.47379787,541.5726390728]]

def distance (p,c):
    """R=6367445 
    res=R*acos(sin(radians(p.latitude))*sin(radians(c.latitude))+cos(radians(p.latitude))*cos(radians(c.latitude))*cos(radians(p.longitude-c.longitude)))"""
    if (res<=0):
        print("Probleme dans calcul distance")
        print(" producteur")
        print(p.name)
        print("Client")
        print(c.name)
        return 30000000000
    return res

def coeffPertes(p,c):
    """resistance lineique dune ligne HT en Ohm/mm 2"""
    rho=3/10**8 
    """section cable moyen ligne HT en mm 2"""
    section=500 
    """Resistance equivalente"""
    Req=rho*distance(p,c)/section 
    """en ampere, intensite moyenne sur un HT"""
    I=400 

    if (p.region==c.region):
        """en Volt"""
        U=90*10**3 
    else:
        """en Volt"""
        U=400*10**3 
        
        """Pour probleme Combinatoire Ou 1-Req*I/U selon utilisation"""
    return Req*I/U 

def findCriticalDistance(TabProd, TabClient):
    distClient=[]
    referent=[]
    for i in range(len(TabClient)):
        mini=distance(TabProd[0],TabClient[i])
        r=TabProd[0]
        print("je change")
        for p in range(len(TabProd)):
            print(TabProd[p].name)
            a=distance(TabProd[p],TabClient[i])
            print(a)
            if a<=mini :
                mini=distance(TabProd[p],TabClient[i])
                r=TabProd[p]
                print(r.name)
                
        distClient.append(mini)           
        referent.append(r)
    """con=1
    for c in range(len(TabClient)):
        for p in range(len(TabProd)):
            if (distance(TabProd[p],TabClient[c])<=distClient[c]):
                print("findCriticalDistance Chie")
    con=0
    if(con==1):
        print("Cest bon, jai bien les bonnes distances")
"""
    """print(distClient)
    for p in referent:
        print(p.name)"""
    maxi=distClient[0]
    for d in distClient:
        if(d>maxi):
            maxi=d
    return maxi


def findCriticalClient(Producteur, TabClient):
    m=0
    clientIndex=0
    for i in range(len(TabClient)):
       if(distance(Producteur,TabClient[i])>distance(Producteur,TabClient[clientIndex])):
           clientIndex=i    
    return TabClient[clientIndex].name

def generateSetPerso(TabProd, TabClient):
    """Generer les sets de solutions possible de facon a ce que tout Client ait au moins un Set le couvrant"""
    D=findCriticalDistance(TabProd, TabClient)
    TabSet=[]
    for i in range(len(TabProd)):
        TabSetIteration=[]
        ClientIteration=[]
        for j in range(len(TabClient)):
            if(distance(TabProd[i],TabClient[j])<=D):
                ClientIteration.append(TabClient[j])

        """Amelioration en triant ClientIteration"""
        while(len(ClientIteration)>0):
            d=findCriticalClient(TabProd[i],ClientIteration)
            TabSetIteration.append(S.Set(TabProd[i],ClientIteration))
            del(ClientIteration[d])
            
        for j in TabSetIteration:
            TabSet.append(j)
        
    return TabSet

def countClientServed(TabSet):
    acc=0
    for s in TabSet:
        acc+=len(s.TabClient)
    return acc

def generateSetSimplified(TabProd, TabClient):
    """Generer les sets de solutions possible de facon a ce que tout Client ait au moins un Set le couvrant"""
    D=findCriticalDistance(TabProd, TabClient)
    TabSet=[]
    for i in range(0,len(TabProd)):
        ClientIteration=[]
        for j in range(len(TabClient)):
            if(distance(TabProd[i],TabClient[j])<=D):
                ClientIteration.append(TabClient[j])

        """Amelioration en triant ClientIteration"""
        TabSet.append(S.Set(TabProd[i],ClientIteration))        
    
    print("Nombre de set")
    print(len(TabSet))
    print("Nombre de client dans les sets")
    print(countClientServed(TabSet))
    print("Nombre de client total")
    print(len(TabClient))
    return TabSet

        
def linearRelaxation(TabSet, TabClient):

    """To solve with cobyla algorithm the relaxed prb 
    min sum(i) x(i)Cout(i)
    CT Pour tout j Sum (i:j)(Si) xi>=1
    CT 0<=xi<=1
    Doesn't work properly for big Sets
   """
    def func(x):
        """To call with x an array of len(TabSet) length"""
        acc=0
        for s in range(len(TabSet)):
            acc+=TabSet[s].coutglobal*x[s]
        return acc
    argsFunc=[]
    alpha=[]
    for i in range(len(TabSet)):
        alpha.append(TabSet[i].coutglobal)

    argsFunc=tuple(a for a in alpha)    
    print(argsFunc)

    cons=[]
    def ctFun2(x,i):
        return x[i]
    def ctFun3(x,i):
        return x[i]+1
    i=0
    while(i<len(TabSet)):
        cons.append(ctFun2)
        i+=1
    i=0
    while(i<len(TabSet)):
        cons.append(ctFun3)
        i+=1
    args=[]
    j=0
    while(j<2):
        for i in range(len(TabSet)):
            args.append([i])
        j+=1
    print(len(cons))
    print(len(args))
    b=np.ones(len(TabSet))
   
    
    """Creation des contraintes"""
    
    def ctFun(x,client,TabSet):
        acc=0
        for i in range(len(TabSet)):
                acc+=TabSet[i].asClient(client)*x[i]
        return acc-1
    
    for i in range(len(TabClient)):
        cons.append(ctFun)
        args.append([TabClient[i], TabSet])

    print(len(cons))
    print(len(args))
    print(args)
    xopt=my_fmin_cobyla(func,b, cons,consargs=args)

    for k in range(len(xopt)):
        if(xopt[k]*log(len(TabClient))>1):
            xopt[k]=1
    return xopt
"""
def linearRelaxation(TabSet, TabClient):
    To solve with simplex the relaxed prb 
    min sum(i) x(i)Cout(i)
    CT Pour tout j Sum (i:j)(Si) xi>=1
    CT 0<=xi<=1
   
    def func(x):
    To call with x an array of len(TabSet) length
        return sum (TabSet[1:].coutglobal*x[1:])

    def func_dev(x):
        a=zeros(len(x))
        for i in range(len(x)):
            a[i]=TabSet[i].coutglobal
            return a
        
    Creation des contraintes
    cons=[{} for j in range(len(TabClient))]
    for j in range(len(TabClient)):
        cons[j]["type"]="inq"
        cons[j]["fun"]=lambda x:np.array(sum(TabSet[1:].asClient(TabClient[i])*x[1:])-1)
        cons[j]["jac"]=lambda x:np.array( TabSet[1:].asClient(TabClient[i]) for h in range(len(TabSet)))

   TESTER ARGS
    xopt=optimi.minimize(func, np.array( 1 for h in range(len(TabSet))), args=(0,1), jac=func_dev, constraints=cons , method='SLSQP', options={'disp': True})
    for k in range(len(xopt)):
        if(xopt[k]*log(len(TabClient))>1):
            xopt[k]=1
    return xopt
"""


def decisionToPickSet(TabProbaSet):
    """   
    1.Generate a number between 0 and 1.
    2. Walk the list substracting the probability of each item from your number.
    3.Pick the item that, after substraction, took your number down to 0 or below.
    Complexity O(n)"""
    TabBooleanSet=np.zeros(len(TabProbaSet))
    b=r.random()
    t=TabProbaSet
    for i in range(len(t)):
        t[i]+=b
        if (t[i]>=1):
            TabBooleanSet[i]=1
    return TabBooleanSet


def repairingFinal(TabSet, TabBooleanSet, TabClient):
    """ Insure that every Client as at minimum one Set covering it"""
    a=[]
    for i in range(len(TabBooleanSet)):
        if (TabBooleanSet[i]==1):
            for j in range(len(TabSet[i].TabClient)):
                a.append(TabSet[i].TabClient[j])
    for i in range(len(TabClient)):
        cond=0
        for j in range(len(a)):
            if (TabClient[i]==a[j]):
                cond=1
                break
        if (cond==0):
            b=[]
            for k in range(len(TabBooleanSet)):
                if (TabBooleanSet[k]==0 & TabSet[k].asClient(i)):
                    b.append(k)
            minb=TabSet[b[0]].coutglobal
            index=b[0]
            for k in range(len(b)):
                if (TabSet[b[k]].coutglobal<TabSet[b[0]].coutglobal):
                    minb=TabSet[b[k]].coutglobal
                    index=b[k]
            TabBooleanSet[index]=1
    return TabBooleanSet

# Interface to Constrained Optimization By Linear Approximation


def my_fmin_cobyla(func, x0, cons, args=(), consargs=None, rhobeg=1.0, rhoend=1e-10,
                iprint=2, maxfun=1000000):
    """
    Minimize a function using the Contrained Optimization BY Linear Approximation
    (COBYLA) method

    Arguments:

    func     -- function to minimize. Called as func(x, *args)

    x0       -- initial guess to minimum

    cons     -- a list of functions that all must be >=0 (a single function
                if only 1 constraint)

    args     -- extra arguments to pass to function

    consargs -- extra arguments to pass to constraints (default of None means
                use same extra arguments as those passed to func).  Use () for no
                extra arguments.

    rhobeg --  reasonable initial changes to the variables

    rhoend --  final accuracy in the optimization (not precisely guaranteed)

    iprint  -- controls the frequency of output: 0 (no output),1,2,3

    maxfun  -- maximum number of function evaluations.


    Returns:

    x -- the minimum
    
    """
    err = "cons must be a list of callable functions or a single"\
              " callable function."
    n = len(x0)
    if isinstance(cons, list):
        m = len(cons)
        for thisfunc in cons:
            if not callable(thisfunc):
                raise TypeError, err
    elif callable(cons):
        m = 1
        cons = [cons]
    else:
        raise TypeError, "cons must be a list of callable functions or a single"\
              " callable function."

    if consargs is None:
        consargs = args
        
    def calcfc(x, con):
        f = func(x, *args)
        k = 0
        for constraints in cons:
            con[k] = constraints(x,*consargs[k])
            k += 1
        return f

    xopt = s._cobyla.minimize(calcfc, m=m, x=x0,rhobeg=rhobeg,rhoend=rhoend,iprint=iprint, maxfun=maxfun)
    return xopt


def greedyAlgorithm(TabSet, TabClient):
    def lonelyClient(BoolTabSet,client):
        for s in range(len(TabSet)):
            if(BoolTabSet[s]*TabSet[s].asClient(client)==1):
                   return 1
        return 0

    def existLonelyClient(BoolTabClient):
        for b in BoolTabClient:
            if (b==0):
                return 1
        return 0
    
    def priceTotalSet(BoolTabSet, Set):
        acc=0
        for i in range(len(BoolTabSet)):
            acc+=BoolTabSet[i]*TabSet[i].coutglobal
        return Set.coutglobal/acc
    
    def findMinCost(BoolTabSet):
        index=0
        while(index<len(BoolTabSet) and BoolTabSet[index]==1): index+=1 
        if(index==len(BoolTabSet)):
            print("It should be terminated")
        
        mini=TabSet[index].coutglobal
        for i in range(index,len(TabSet)):
            if(BoolTabSet[i]==0 and TabSet[i].coutglobal<mini):
                index=i
                mini=TabSet[i].coutglobal
        return index
            
    def findClient(client):
        for i in range(len(TabClient)):
            if (client.key==TabClient[i].key):
                return i
        return len(TabClient)
    
    """Test findClient"""
    acc=0
    for i in range(len(TabClient)):
        if(findClient(TabClient[i])!=i):
            acc+=1
            print("findClient Chie")

    BoolTabClient=np.zeros(len(TabClient))
    BoolTabSet=np.zeros(len(TabSet))
    PriceTabSet=np.zeros(len(TabSet))

    while (existLonelyClient(BoolTabClient)):
        index=findMinCost(BoolTabSet)
        BoolTabSet[index]=1
        for i in range(len(TabSet[index].TabClient)):
            BoolTabClient[findClient(TabSet[index].TabClient[i])]=1
    return BoolTabSet
            
        

    
"""
def toPlotEdges(TabSet, TabBooleanSet):
    return any inforation needed to plot edges
    return ?
    
"""
